Virtually all complex integrated circuits are designed with the use of computer aided design (CAD) tools. Some CAD tools, called simulators, help the circuit designer verify the operation of a proposed circuit. Another type of CAD tool, called a silicon compiler (also sometimes known as automatic layout or place and route systems), generates the semiconductor mask patterns from a detailed circuit specification. These semiconductor mask patterns for a particular circuit are commonly called the "circuit layout".
Circuit layouts have multiple overlapping mask layers for defining different mask levels (also called layout levels) of a semiconductor integrated circuit. For instance, some layers of the circuit layout will define the regions of the semiconductor substrate that are doped with N-type or P-type dopants, while other layers of the circuit layout will define regions in which materials are deposited on the top of the substrate, such as polysilicon and metal regions, while yet other layers will define apertures to be formed in various layers of material so as to form connections between layers of the semiconductor circuit.
Each layer of a circuit layout is defined as a set of polygons or cells. In some systems, the cells must be rectangles, but most circuit layout systems allow the use of trapezoids and/or polygons whose sides are all vertical, horizontal or at a 45-degree angle to such vertical and horizontal sides.
Typically, a circuit layout will be prepared for a particular set of design rules. For instance, one will often hear that a circuit was manufactured using "2 micron design rules" or "2 micro minimum critical dimensions". Such phrases mean that certain features of the circuit's layout have minimum widths of 2 microns. Later, a faster version of that same circuit may be manufactured using "1 micron design rules" or "1 micron minimum critical dimensions".
While a number of attempts have been made in the past to compress or compact circuit layouts using automated computer techniques, most such prior automatic circuit layout compression systems use graph theory or linear programming methods, and thus lose at least some of the useful information and optimizations in the original layout. In addition, many of the prior art techniques are unable to handle layouts that include polygons with sides at 45 degree angles, and most require so many computer operations as to be impractical commercially.
One method for compacting integrated circuit layouts in known as the constraint graph method, which involves generating a layout data structure for an input layout, and then generating an additional, graphically based data structure. The layout is minimized using a "longest paths" algorithm, which involves finding the longest path through "edges" (or paths) through "nodes" of the layout, where the node indicate locations of cells. These longest paths are reduced by modifying positions of the cells, to make the layout smaller.
The constraint graph method does not present an efficient means for sizing transistors, which are subject to different design rules than other cells in a layout. In addition, it requires the use of the additional, graphical data structure, which presents a N.sup.2 problem to the processor, N being the number of cells in the layout.
Other current layout compaction procedures are not efficient at handling compaction of layouts, and in particular at resizing transistors as desired during such compaction.